/**
 * 时间复杂度 O(n^2)
 * 空间复杂度 O(1)
 */
console.log('---------------------优化前的冒泡算法-----------------------------');

function worstBubbleSort(nums) {
	// 冒泡排序
	for (let i = 0; i < nums.length; i++) { //控制循环次数
		for (let j = 0; j < nums.length - 1; j++) { //控制内层循环
			if (nums[j] > nums[j + 1]) {
				let temp = nums[j];
				nums[j] = nums[j + 1]
				nums[j + 1] = temp
			}
		}
		console.log(`第${i}次:`, nums);
	}
	return nums
}
const colors = [3, 4, 5, 7, 3, 5, 8]
worstBubbleSort(colors)

console.log('---------------------优化后的冒泡算法-----------------------------');
/*
 *优化外层循环：记录当前循环中是否发生了变化，如果没有变化则直接结束
 *优化内层循环：记录当前循环中最后一次元素交换的位置，该位置以后的序列都是已经排列好的序列，单独放一个数组里面，下一轮循环的时候无需再去比较
 */
function bestBubbleSort(nums) {
	let numsLength = nums.length - 1
	for (let i = 0; i < nums.length; i++) {
		let isChanged = 0
		let lastPosition = 0
		for (let j = 0; j < numsLength; j++) {
			if (nums[j] > nums[j + 1]) {
				let temp = nums[j]
				nums[j] = nums[j + 1]
				nums[j + 1] = temp
				isChanged++
				lastPosition = j //最后一次交换的位置
			}
		}
		console.log(`第${i}次`, nums);
		if (isChanged == 0) break //说明顺序是正确的，直接结束整个循环
		numsLength = lastPosition //缩短内层循环的遍历次数
	}
	return nums
}
var nums = [3, 4, 5, 7, 3, 5, 8]
bestBubbleSort(nums)